package hot100;


/*
 * Author：江松
 * Date：2023/4/6 10:39
 *
 最大正方形：
 1，暴力法：分别枚举每个正方形（对角线顶点）进行检验和计算

 2，动态规划：

 官方题解dp表示的是边长，这样能减少开方平方的计算

 dp(i,j)=以(i,j)结尾的正方形面积的最大值
划分为几种情况：
当前点为0，
当前点不为0，需要由上一个正方形转移，
上一个最优子结构就是这旁边3个正方形的公共部分组成，然后取边长最小值进行计算转移
 */

public class Main221 {
    public int maximalSquare(char[][] matrix) {
        int n=matrix.length,m=matrix[0].length;
        int dp[][]=new int[n+5][m+5];
        int res=Integer.MIN_VALUE;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                char ch=matrix[i-1][j-1];
                if(ch=='0'){
                    dp[i][j]=0;
                }else{
                    int ai=(int)Math.sqrt(dp[i-1][j]);
                    int aj=(int)Math.sqrt(dp[i][j-1]);
                    int aa=(int)Math.sqrt(dp[i-1][j-1]);//分别计算出边长取最小值
                    int a=Math.min(Math.min(ai,aj),aa)+1;
                    dp[i][j]=a*a;
                }
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
    }

    /*
        public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    // 遇到一个 1 作为正方形的左上角
                    maxSide = Math.max(maxSide, 1);
                    // 计算可能的最大正方形边长
                    int currentMaxSide = Math.min(rows - i, columns - j);
                    for (int k = 1; k < currentMaxSide; k++) {
                        // 判断新增的一行一列是否均为 1
                        boolean flag = true;
                        if (matrix[i + k][j + k] == '0') {
                            break;
                        }
                        for (int m = 0; m < k; m++) {
                            if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            maxSide = Math.max(maxSide, k + 1);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
     */
}
